import collections


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        node = root
        stack = collections.deque([node])
        out = collections.deque()
        while stack:
            node = stack[-1]
            out.append(str(node.val))
            if node.left:
                stack.append(node.left)
            else:
                node = stack.pop()
                while stack and not node.right:
                    node = stack.pop()
                if node.right:
                    stack.append(node.right)
        return ','.join(out)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        data = data.split(',')
        root = TreeNode(int(data[0]))
        node = root
        stack = collections.deque([node])
        for i in range(1, len(data)):
            val = int(data[i])
            new_node = TreeNode(val)
            if val < stack[-1].val:
                node.left = new_node
                node = new_node
                stack.append(node)
            else:
                while stack and stack[-1].val < val:
                    node = stack.pop()
                node.right = new_node
                node = new_node
                stack.append(node)
        return root

                


